package com.zp.self.module.level_4_算法练习.数据结构.二叉树;

import java.util.Stack;

public class 力扣_100_相同的树 {
    public static void main(String[] args) {
        TreeNode root = TreeNode.initRoot();
        System.out.print(new 力扣_100_相同的树().isSameTree2(root,root));

    }

    /**
     题目：给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。
     如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。

     分析：
     ×想法1：分别遍历，生成字符串[]  ，最后对比字符串是否相同
     √想法2：同时遍历  if(val == val )
     √想法3--借鉴：递归遍历

     边界值 & 注意点：
     1.都为null,一个为null
     **/
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if(p==null && q==null)return true;
        if(p==null || q==null)return false;
        Stack<TreeNode> stack0 = new Stack<>();
        Stack<TreeNode> stack1 = new Stack<>();
        stack0.push(p);
        stack1.push(q);
        while (!stack0.isEmpty()) {
            TreeNode peek0 = stack0.peek();
            TreeNode peek1 = stack1.peek();
            if(peek0==null || peek1==null || peek0.val != peek1.val)return false;
            if(peek0.left!=null || peek1.left!=null ){
                stack0.push(peek0.left);
                stack1.push(peek1.left);
                peek0.left =null;
                peek1.left =null;
                continue;
            }
            stack0.pop();stack1.pop();
            if(peek0.right!=null || peek1.right!=null){
                stack0.push(peek0.right);
                stack1.push(peek1.right);
                peek0.right=null;
                peek1.right=null;
            }
        }
        return true;
    }

    public boolean isSameTree2(TreeNode p, TreeNode q) {
        if(p==null && q==null)return true;
        if(p==null || q==null || p.val!= q.val)return false;
        return isSameTree2(p.left, q.left) && isSameTree2(p.right, q.right);
    }
}
